//有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，
//5，7，9，15，21。 
//
// 示例 1： 
//
// 
//输入：k = 5
//输出：9
// 
//
// Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 257 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-09-15 23:18:28
 * @description 面试题 17.09.第 k 个数
 */
public class GetKthMagicNumberLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 GetKthMagicNumberLcci fun=new GetKthMagicNumberLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int getKthMagicNumber1(int k) {
		List<Integer> ans = new ArrayList<>();
		ans.add(1);
		int a = 0, b = 0, c = 0;
		// 维护三个变量，每次加入一个，所有的答案都是3 ， 5  ，7 的倍数
		for (int i = 0; i < k - 1; i++) {
			// dp[a]*3.dp[b]*5.dp[c]*7都大于dp[i-1]，dp[a-1]*3.dp[b-1]*5.dp[c-1]*7都小于等于dp[i-1]
			//dp[i]=min(dp[a]*3.dp[b]*5.dp[c]*7),则dp[i]>dp[i-1]且dp[i]是大于dp[i-1]的最小值
			// 更新abc指针计算dp[i+1]
			int next = Math.min(ans.get(a) * 3, Math.min(ans.get(b) * 5, ans.get(c) * 7));
			ans.add(next);
			// 3 5 7 9 15 21
			// 9是a。15是b,21是c
			// 如果相等，都会+1，所以不会重复，
			if (next == ans.get(a) * 3) a++;
			if (next == ans.get(b) * 5) b++;
			if (next == ans.get(c) * 7) c++;
		}

		return ans.get(ans.size() - 1);
	}
	// 优先队列
	public int getKthMagicNumber(int k) {
		int[] factors = {3, 5, 7};
		Set<Long> seen = new HashSet<Long>();
		PriorityQueue<Long> heap = new PriorityQueue<Long>();
		seen.add(1L);
		heap.offer(1L);
		int magic = 0;
		for (int i = 0; i < k; i++) {
			long curr = heap.poll();
			magic = (int) curr;
			for (int factor : factors) {
				long next = curr * factor;
				// 因为可能重复，去重，可以多添加，但是只出队了k次
				if (seen.add(next)) {
					heap.offer(next);
				}
			}
		}
		return magic;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
